/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/coins-in-a-line-ii
   @Language: C++
   @Datetime: 16-02-09 05:44
   */

// Method 1
class Solution {
public:
	/**
	 * @param values: a vector of integers
	 * @return: a boolean which equals to true if the first player will win
	 */
	bool firstWillWin(vector<int> &values) {
		// write your code here
		int n=values.size(), sum=0;
		vector<int> dp(n,0);  // dp[i], select i and [i,n) max
		for(int i=n; i--;){
			int a=i+1<n?values[i+1]:0;
			int b=i+2<n?dp[i+2]:0;
			int c=i+3<n?dp[i+3]:0;
			int d=i+4<n?dp[i+4]:0;
			dp[i]=max(values[i]+min(b,c),values[i]+a+min(c,d));
			sum+=values[i];
		}
		return dp[0]>sum-dp[0];
	}
};


// Method 2
class Solution {
public:
	/**
	 * @param values: a vector of integers
	 * @return: a boolean which equals to true if the first player will win
	 */
	bool firstWillWin(vector<int> &values) {
		// write your code here
		if(values.size()<3) return true;
		int n=values.size();
		vector<int> first(n,0), second(n,0);	// select i and [i,n) max
		first[n-1]=values[n-1];
		first[n-2]=values[n-1]+values[n-2];
		for(int i=n-2; i--;){
			int a=values[i]+second[i+1];
			int b=values[i]+values[i+1]+second[i+2];
			first[i]=max(a,b);
			second[i]=(a<b?first[i+2]:first[i+1]);
		}
		return first[0]>second[0];
	}
};
